package com.lishem.carl._07tree;

import com.lishem.common.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
 * <p>
 * 如果树中有不止一个众数，可以按 任意顺序 返回。
 * <p>
 * 假定 BST 满足如下定义：
 * <p>
 * 结点左子树中所含节点的值 小于等于 当前节点的值
 * <p>
 * 结点右子树中所含节点的值 大于等于 当前节点的值
 * <p>
 * 左子树和右子树都是二叉搜索树
 */
public class _29LetCode501_二叉搜索树中的众数 {

    public int[] findMode(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode pre = null;
        int maxCount = 0;
        int count = 0;
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                if (pre == null || pre.val != root.val){
                    count = 1;
                }else {
                    count++;
                }
                if (count > maxCount) {
                    maxCount = count;
                    list.clear();
                    list.add(root.val);
                } else if (count == maxCount) {
                    list.add(root.val);
                }
                pre = root;
                root = root.right;
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        _29LetCode501_二叉搜索树中的众数 sol = new _29LetCode501_二叉搜索树中的众数();
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(2);
        System.out.println(Arrays.toString(sol.findMode(root)));
    }
}
